CS254 Spring 2003Practice Midterm 1

The practice midterm is below. Here are some facts about the actual midterm: (a) The midterm will be in class . (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (f) One problem (less typos) on the actual test will be from the practice test.

1. Show directly that N! is O(e^{n log n}).

2. Give a TM (either a diagram or give its transition table you can use more than one tape) that takes an input x and ouputs the string x in reverse.

3. Redo problem 2. But this time give a RAM that does the same thing.

4. Show that that the language

L={x;y;z : x,y,z are strings over {0,1} such that x+y=z }

is in LOGSPACE.

5. Suppose L is decided by a one-tape machine M in time f(n). Show there is a k-tape machine M' for some k that uses the same alphabet as M and decides L in time εf(n) + n + 2.

6. Show the language L=

{<M> : for each n, M accepts exactly half the strings of length n}

is not recursive.

7. A many-one reduction from one language L to another L' is a recursive function f such that x ∈L iff f(x)∈L'.

Show the halting problem language H is not many-one reducible to the complement of H.

8. A circuit C is monotone if it does not use NOT gates. The function HALF_n(x₁,...x_n) is true iff at least half of its inputs are true. Give a monotone circuit for HALF_n.

9. Prove that if f and g are proper complexity functions so is f + g.

10. Prove coNTIME(N²)is not a subset of NTIME(N).